edu.claflin.finder.logic

Class BronKerboschBipartiteUtils

java.lang.Object

edu.claflin.finder.logic.BronKerboschBipartiteUtils

public class BronKerboschBipartiteUtils
extends java.lang.Object

Provides methods to mark graphs as bipartite using the basic Graph, Edge, and Node classes. Mostly copy-pasted from BipartiteCondition, but modified slightly to be able to mark nodes and return them. To my knowledge the only thing that actually mark nodes uses CytogrouperNode which is a bit different. This class should rectify that.

Author:

kpuli007

Constructor Summary

Constructors

Constructor and Description
BronKerboschBipartiteUtils()

Method Summary

Modifier and Type	Method and Description
static java.util.ArrayList<java.util.ArrayList<Node>>	bipartiteDivision(Graph existingGraph) Divides the given graph into bipartite sets.
static java.util.ArrayList<java.util.ArrayList<Node>>	constructArrayList(java.util.Set<Node> groupA, java.util.Set<Node> groupB) Constructs array list of array lists from sets.
private static boolean	satisfies(Graph existingGraph, java.util.Set<Node> addSet, java.util.Set<Node> compareSet, Node current) Private method for stepping through the adjacency lists and determining if the graph is bipartite.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BronKerboschBipartiteUtils

public BronKerboschBipartiteUtils()

Method Detail

bipartiteDivision

public static java.util.ArrayList<java.util.ArrayList<Node>> bipartiteDivision(Graph existingGraph)

Divides the given graph into bipartite sets.

Returns:

two lists of nodes, each representing a bipartite group. Both lists are empty if the graph is not a valid bipartite graph.

constructArrayList

public static java.util.ArrayList<java.util.ArrayList<Node>> constructArrayList(java.util.Set<Node> groupA,
                                                                                java.util.Set<Node> groupB)

Constructs array list of array lists from sets. Array lists are used over sets to make traversing the graph's nodes (see Graph.addEdgesBetweenAllNodesInList(ArrayList)) possible.

Parameters:

groupA - first output set

groupB - second output set

Returns:

array list containing the two sets as array lists

satisfies

private static boolean satisfies(Graph existingGraph,
                                 java.util.Set<Node> addSet,
                                 java.util.Set<Node> compareSet,
                                 Node current)

Private method for stepping through the adjacency lists and determining if the graph is bipartite. Specifically, it uses a Depth-First model for exploring the node tree and sorting the nodes into two groups. If it successfully sorts the nodes into two groups with no invalidating edges, it returns true.

Parameters:

existingGraph - the Graph object to test against.

addSet - the current set to add a node to based on the previous.

compareSet - the current set to add adjacent nodes to.

current - the current Node being compared.

Returns:

true if the structure could be bipartite.